59E - Shortest Path - CodeForces Solution

#include<iostream>
#include<set>
#include<queue>
#include<map>
#include<utility>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<string.h>
using namespace std;
#define int long long
const int INF=1e15;
const int mod=1e9 + 7;
int gcd(int a, int b)
{
	if (a == 0)
		return b;
	return gcd(b % a, a);
}
const int N=3001;
set<pair<int,int> >  bad[3001];
vector<int> adj[N];
void solve(){
	int n,m,k;
	cin>>n>>m>>k;
	for(int i=0;i<m;i++){
		int a,b;
		cin>>a>>b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	for(int i=0;i<k;i++){
		int a,b,c;
		cin>>a>>b>>c;
		bad[c].insert(make_pair(a,b));
	}

	int p[n+1][n+1];

	p[1][1]=0;
	bool flag =0;
	vector<vector<int> > d(n+1,vector<int> (n+1,-1));
	d[1][1]=0;
	queue<pair<int,int> > q;
	pair<int,int> ans;
	q.push(make_pair(1,1));
	while(!q.empty()){
		pair<int,int> u=q.front();
		q.pop();
		if(u.second==n){
			flag=1;
			ans=u;
			break;
		}
		for(int v : adj[u.second]){
			if(bad[v].count(u)!=0){
				continue;
			}
			if(d[u.second][v]==-1){
				d[u.second][v]=d[u.first][u.second]+1;
				p[u.second][v]=u.first;
				q.push(make_pair(u.second,v));
			}
		}
	}
	if(!flag){
		cout<<-1<<endl;
		return;
	}
	cout<<d[ans.first][ans.second]<<endl;
	vector<int> aa;
	int v=n;
	int pp=ans.first;
	while(v!=1){
		aa.push_back(v);
		v=pp;
		pp=p[pp][aa[aa.size()-1]];
	}
	reverse(aa.begin(),aa.end());
	cout<<1<<" ";
	for(int x : aa){
		cout<<x<<" ";
	}
}
signed main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t=1;
	// cin>>t;
	while(t--){
		solve();
	}
}